# 

# 

# ID3算法是一种经典的决策树学习算法，由Ross Quinlan在1986年提出。该算法基于信息论中的信息增益原理来选择划分属性，从而构建决策树。下面我将对ID3算法进行详细解释，并提供一个Python代码示例。

# 

# ### ID3算法解释

# 

# ID3算法的核心思想是通过计算每个属性的信息增益来评估其作为划分属性的好坏。信息增益表示在给定属性条件下，数据集不确定性减少的程度。具体来说，ID3算法首先计算整个数据集的初始熵（即不确定性），然后计算每个属性划分数据集后的条件熵，最后通过比较初始熵和条件熵的差值（即信息增益）来选择最佳划分属性。

# 

# 在ID3算法中，每个节点表示一个属性，每个分支表示该属性的一个可能取值，每个叶子节点表示一个类别。算法从根节点开始，选择信息增益最大的属性作为当前节点的划分属性，然后根据该属性的不同取值将数据集划分为若干个子集，每个子集对应一个分支。接着，对每个子集递归执行上述过程，直到所有子集都属于同一类别或没有更多属性可供划分为止。

# 

# ### Python代码示例

# 

# 下面是一个使用Python实现ID3算法的简单示例。该示例假设输入数据集是一个二维列表，其中每个内部列表表示一个样本，第一个元素是类别标签，其余元素是特征值。

# 

# 

import math

from collections import Counter



def calc_entropy(data):

    """计算数据集的熵"""

    labels = [row[0] for row in data]

    num_entries = len(labels)

    label_counts = Counter(labels)

    ent = 0.0

    for key in label_counts:

        prob = float(label_counts[key]) / num_entries

        ent -= prob * math.log(prob, 2)

    return ent



def split_data(data, axis, value):

    """根据属性值划分数据集"""

    ret_data = []

    for feat_vec in data:

        if feat_vec[axis] == value:

            reduced_feat_vec = feat_vec[:axis]

            reduced_feat_vec.extend(feat_vec[axis+1:])

            ret_data.append(reduced_feat_vec)

    return ret_data



def choose_best_feature_to_split(data):

    """选择最佳划分属性"""

    num_features = len(data[0]) - 1

    base_entropy = calc_entropy(data)

    best_info_gain = 0.0

    best_feature = -1

    for i in range(num_features):

        feat_list = [example[i] for example in data]

        unique_vals = set(feat_list)

        new_entropy = 0.0

        for value in unique_vals:

            sub_data = split_data(data, i, value)

            prob = len(sub_data) / float(len(data))

            new_entropy += prob * calc_entropy(sub_data)

        info_gain = base_entropy - new_entropy

        if (info_gain > best_info_gain):

            best_info_gain = info_gain

            best_feature = i

    return best_feature



# 示例数据集（类别标签在前，特征值在后）

data = [['no', 'sunny', 'hot', 'high', 'weak'],

        ['no', 'sunny', 'hot', 'high', 'strong'],

        ['yes', 'overcast', 'hot', 'high', 'weak'],

        # ... 省略其他样本

       ]



# 选择最佳划分属性

best_feature = choose_best_feature_to_split(data)

print(f"Best feature to split on is: {best_feature}")
